4、方格填数
题目 方格填数
思路分析
可以直接全排列出来0~9的组合 再把每个数对应到格子里去比对
也可以像n皇后那样 从每个格子考虑 确定当前放什么 然后下一个格子能放什么……
代码实现
#include<bits/stdc++.h>
using namespace std;
string s="0123456789";
bool check(char a,char b){
if(abs(int(a)-int(b))==1)
return false;
return true;
}
int main(){
int cnt=0;
do {
if(
check(s[0],s[1]) && check(s[0],s[3]) && check(s[0],s[4]) && check(s[0],s[5])
&&
check(s[1],s[2]) && check(s[1],s[4]) && check(s[1],s[5]) && check(s[1],s[6])
&&
check(s[2],s[5]) && check(s[2],s[6])
&&
check(s[3],s[4]) && check(s[3],s[7]) && check(s[3],s[8])
&&
check(s[4],s[5]) && check(s[4],s[7]) && check(s[4],s[8]) && check(s[4],s[9])
&&
check(s[5],s[6]) && check(s[5],s[8]) && check(s[5],s[9])
&&
check(s[6],s[9])
&&
check(s[7],s[8])
&&
check(s[8],s[9])
)
cnt++;
}while (next_permutation(s.begin(), s.end()));
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[4][5]={-20};
bool st[10];
int dx[4]={-1,-1,-1,0};
int dy[4]={0,1,-1,-1};
int sum;
bool check(int x,int y,int n){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<3 && nx>=0 && ny>=0 && ny<4){
if(abs(a[nx][ny]-n)==1)
return false;
}
}
return true;
}
void dfs(int x,int y){
if(x==2 && y==3){
sum++;
return;
}
for(int i=0;i<10;i++){
if(!st[i] && check(x,y,i)){
st[i]=true;
a[x][y]=i;
if(y+1<4)
dfs(x,y+1);
else
dfs(x+1,0);
st[i]=false;
a[x][y]=-20;
}
}
}
int main()
{
dfs(0,1);
cout<<sum;
return 0;
}
💬 评论